package a_topologicalSort;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 每次选取入度为0的点，加入队列，然后删除相应边。
 * 直到队列为空。
 * 加入队列代表访问过该点，若访问过的点个数小于图中点数，则有环。
 * 
 * @author I321035
 *
 */
public class BFS {
	public static void main(String[] args){
		BFS b=new BFS();
		boolean[][] graph=new boolean[4][4];
		graph[0][1]=true;
		graph[2][1]=true;
		graph[1][3]=true;
//		graph[3][1]=true;
		b.topologicSort(graph);
	}
	
	
	public void topologicSort(boolean[][] graph){
		List<Integer> result=bfs(graph);
		if(result.size()<graph.length)
			System.out.println("有环！");
		else
			System.out.println(result.toString());
	}
	
	public List<Integer> bfs(boolean[][] graph){
		Queue<Integer> queue=new LinkedList<>();
		int[] inDegree =new int[graph.length];
		for(int i=0;i<graph.length;i++){
			for(int j=0;j<graph[i].length;j++){
				if(graph[i][j])
					inDegree[j]++;
			}
		}
		for(int i=0;i<inDegree.length;i++){
			if(inDegree[i]==0)
				queue.add(i);
		}
		List<Integer> result=new LinkedList<>();
		while(!queue.isEmpty()){
			int top=queue.poll();
			result.add(top);
			for(int i=0;i<graph[0].length;i++){
				if(graph[top][i]){
					inDegree[i]--;
					if(inDegree[i]==0){
						queue.add(i);
					}
				}
			}
		}
		return result;
	}
}
